\begin{section}{Desarrollo}

El trabajo consistió en desarrollar un algoritmo de 'Cañon Warp' \footnote{Ver {\sf Apéndice A}}. Dicho cañon debía poder calcular la pocisión enemiga resolviendo los sistemas lineales que se presentaron en el problema, y generar una matriz de disparo tal que al enemigo no le sea fácil resolver el sistema lineal que se le presente.

\begin{subsection}{Estrategias}
\begin{subsubsection}{Primeras ideas: Matar o Morir}
La primera estrategia que desarrollamos consistía en enviar una modificación de la matriz de Hilbert (que se explicara mas adelante en esta sección) todos los turnos. La idea consistia en enviar una matriz lo suficientemente complicada para que no pueda ser descifrada, sin importar a donde se efectue el disparo. Se planteo una constante de N cantidad de turnos donde dispararíamos (sin importar a donde) diferentes modificaciones de Hilbert hasta que en el turno N generaríamos de forma sencilla con una matriz diagonal que dispare al promedio de todas las posiciones calculadas de la nave enemigo en los turnos anteriores. De esta forma se pretendía sobrevivir a los primeros N disparos y arriesgarlo todo en el último.
El problema que esta estrategia presentaba era la dificultad de encontrar un N óptimo, ya que con un N muy grande le dábamos oportunidad al rival para que nos destruya, y un N pequeño no nos daba tiempo a conseguir el disparo. Desistimos con esta estrategia ya que esto varía según la táctica defensiva y ofensiva de cada rival. Esta estrategia no llego a ser implementada completamente, con lo que sólo la analizamos de forma preliminar, sin mayor profundidad que la descrita en esta subsección.  
\end{subsubsection}

\begin{subsubsection}{Modificación de Hilbert}
La segunda estrategia que se pensó y acabó por ser la elegida, fue de generar en cada turno una matriz de hilbert modificada. Para estp se reemplazó la primer vector columna por un nuevo vector tal que al multuplicar esta matriz por nuestra posición se disparé a la posicion enemiga previamente calculada.  

\vspace{0.5cm}
\noindent{\bf Estrategia de Defensa:}
\vspace{0.3cm}


Para la estrategia de defensa se utilizó una modificación de la matriz de Hilbert, que como se menciono anteriormente es muy mal condicionada. Sin embargo, se agrego una constante \text{C} $\in \mathbb{N}$, la que se le sumo al denominador de cada $H_{ij}$. Al hacer esto, se trabaja con números mucho mas pequeños sin perder ninguna de las propiedades de la matriz de hilbert. Esto sucede porque esta matriz en realidad es una submatriz cuadrada de una matriz de hilbert de mayor dimension. Por ejemplo, sea $H_{k}$ la matriz de hilbert a la que se le suma la constante \text{C} a cada denominador $\in \mathbb{R}^{3x3}$. Si tomamos \text{C = 3}, nos quedaria la siguiente matriz:

$$
\begin{bmatrix}
\frac{1}{3} & \frac{1}{4} & \frac{1}{5} \\
\frac{1}{4} & \frac{1}{5} & \frac{1}{6} \\
\frac{1}{5} & \frac{1}{6} & \frac{1}{7} \\
\end{bmatrix}
$$

Y esto no es más que una submatriz de la matriz de Hilbert de $\mathbb{R}^{4x4}$

$$
\begin{bmatrix}
\frac{1}{1} & \frac{1}{2} & \frac{1}{3} & \frac{1}{4}\\ 
\frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5}\\
\frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6}\\
\frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{1}{7}\\
\end{bmatrix}
$$

Sabemos que Hilbert es Totalmente Positiva, con lo que sabemos que el determinante de cualquier submatriz cuadrada es mayor que 0, con lo que cualquier submatriz cuadrada es inversible. Esperamos que al tomar una submatriz con coeficientes más pequenñs, el número de condición se agrandará, dificultandole a los programas enemigos poder calcular la inversa de nuestra matriz de disparo y así evitar ser descubiertos.

Con cada turno que pasa se modifica la constante que se suma al denominador de cada coeficiente para enviar dos veces la misma matriz de disparo y para que a medida que nuestro enemigo vaya aproximando nuestra posición le enviamos matrices cada con un \text{C} cada vez mas grande, esperando de cada nueva matriz un peor condicionamiento para luego hacer menos preciso su disparo de respuesta.

Para el primer Disparo se dispara con la matriz original de Hilbert y \text{C} = 250. Para cada turno nº N se calcula la matriz de disparo utilizando como base la matriz de Hilbert y un \text{C} = 51 + 10*N. Estos números fueron decididos de forma empírica mediante las evaluaciones en la sección \text{Resultados}. Estos valores iniciales fueron valores arbitrarios con los que se comenzaron las evaluaciones.
\vspace{0.5cm}
\noindent{\bf Estrategia de Ataque:}
\vspace{0.3cm}

Para poder efectuar el disparo, primero hubo que calcular la posicion enemiga utilizando la matriz de último ataque enemigo junto con su disparo correspondiente. Sabiendo que \\
$Ay=d$  la fórmula del disparo enemigo, para hallar $y$ se debia hallar $A^{-1}$, que siempre existe ya que es condición pedida por enunciado, y hacer el calculo

$$y=A^{-1}d$$ 

Para calcular la inversa utilizamos el algoritmo de Eliminacion Gaussiana con pivoteo parcial descrito anteriormente. Otro enfoque posible hubiera sido plantear un sisema lineal y resolverlo con algoritmos reducción de matrices como QR\footnote{Ver {\sf Apoximación de los valores característicos, 9.4 Algorítmo QR} en {\em Análisis Numérico}\cite{burden} } , pero al no poder hacer un implementación funcional y precisa en el tiempo acotado que se nos dio tuvimos que optar por el algorítmo de Eliminacion Gaussiana.

Una vez calculada $A^{-1}$, se la multiplico por el vector disparo del enemigo para así conseguir la posición del programa rival.

En cada turno, no se intenta disparar a la última posición calculada, sino que se calcula la posible posición del cañon enemigo, se almacena y se saca un promedio de los ultimos 5 disparos y se dispara hacia ese lugar. Pensamos en esta opción pues con al no saber a priori la estrategia de ataque de nuestro rival, no sabemos cuan mal condicionadas pueden ser sus matrices de disparo y los resultados calculados por nuestro algoritmo puedan ser muy imprecisos, con lo que promediar con todas las posiciones anteriores calculadas puede llevar al acarreo de un error de precisión significativo.

La forma de generar la matriz de disparo, es tomar la matriz de hilbert modificada, donde el \text{C} que se le suma al denominador varía en cada turno, y se reemplazo la columna \text{i} tal que la coordenada \text{i} correspondiente a nuestra posición sea no nula, y se calcula cada coordenada del nuevo vector columna despejando de la siguiente manera:\\

Por simplicidad de notación, asumiremos que la coordenada \text{i} no nula de nuestro vector posición es la coordenada numero 1.

Sea \text{H'} la matriz de hilbert modificada con la primera columna como incógnita, \text{x} nuetro vector posición y \text{d'} la posición a donde queremos disparar.

De esta forma la multiplicacion \text{H'. x} = \text{y'} nos plantearía el siguiente sistema
\begin{align*}
	H'_{1,1} x_{1} + \dfrac{1}{2+c} x_{2} + ... + \dfrac{1}{n+c} x_{n}  &=  d'_{1} \\
	&\vdots \\
	H'_{n,1} x_{1} + \dfrac{1}{n+1+c} x_{2} + ... + \dfrac{1}{2n-1+c} x_{n} &= d'_{n}	
\end{align*}
Luego despejamos
\begin{align*}
	H'_{1,1} &= (d' - \dfrac{1}{2+c} x_{2} - ... - \dfrac{1}{n+c} x_{n} )/x_{1} \\
	&\vdots \\
	H'_{n,1} &= (d'_{n} - \dfrac{1}{n+1+c} x_{2} - ... - \dfrac{1}{2n-1+c} x_{n} )/x_{1} 	
\end{align*}
De esta forma, al ser la matriz original mal condicionada, al cambiar una columna, si bien el numero de condición no será el mismo, esperamos que se mantenga con un número de condicion alto (ver la sección \text{Resultados}) que no sea facil de descifrar, y también se logra disparar al vector posición deseado.

Sin embargo, existen casos donde esta matriz de disparo \text{H'} resulta ser una matriz singular, ya que el vector columna que le agregamos para poder disparar a donde nosotros queremos resulte ser una combinacion lineal del resto de las columnas de \text{H'}.Sin embargo, como analizaremos en el \text{Apendice I} y se podrán observar pruebas en la sección de \text{Resultados} la probabilidad de que esto ocurra es depreciable. 

Ya que estas matrices trabajan con valorse muy pequeños realizar pruebas para verificar su inversibilidad mediante el calculo del determinante podría pasar que calcular un determinante de distinto de 0 aun siendo esta en realidad singular, por los errores numéricos que se acarrean al operar con aritmética finita. Es por esto que en lugar de realizar esta prueba con la matriz de hilbert, elegimos una matriz M arbitraria, inversible y bien condicionada junto con pares aleatorios de vectores de origen y destino (de la misma forma que los pares de vectores generados por el Arbitro provisto por la materia), para convertirla en una matriz de disparo y luego realizar las operaciones con el determinante y poder evaluar si efectivamente la probabilidad de generar una matriz de disparo singular es baja.

Para poder evaluar el correcto funcionamiento del programa, se lo hizo competir contra los programas de otros grupos de la materia. Estos grupos fueron los de De Sousa Bispo Mariano y Livorno Carla (luego de ser evaluado por los docentes de la materia) y el de Ciraco Agustina y Heredia Nadia (versión aún no corregida por la cátedra). Se realizaron corridas variando la dimensión del espacio vectorial de la competencia. 

\end{subsubsection}
\end{subsection}



\end{section}
